In recent years, virtualization has re-emerged as a means to improve utilization of available compute power and to enhance overall system reliability. However, virtualization overhead has become a major obstacle for mainstream adoption. One of the major overheads of virtualization is related to increased misses in certain memory structures such as a translation lookaside buffer (TLB). While performance improvement can be achieved by tagging the TLBs and avoiding a TLB flush during a virtual machine (VM) context switch, this makes the TLB structures a shared resource between multiple VMs. As with any shared resource, its performance within a VM context will then be impacted heavily by other VMs' use of the TLB. For example, a streaming application which touches several pages of memory may potentially use up all the TLB entries, wiping out the entries associated with the other VMs. This can adversely affect the performance of these other VMs when they get scheduled later, leading to both degraded and non-deterministic performance of VMs in a consolidated environment.